
public class SinglyList<T> extends Object{

    public Node<T> head;
    public SinglyList(){
        this.head = new Node<>();
    }
    public SinglyList(T[] val){
        this();
        Node<T> cur = this.head;
        for (int i = 0; i < val.length; i++) {
            if(val[i] != null){
                cur.next = new Node<>(val[i],null);
                cur = cur.next;
            }
        }
    }
    public boolean isEmpty(){
        return this.head.next == null;
    }
    public T get(int i){
        Node<T> cur = head.next;
        while(cur != null && i > 0){
            cur = cur.next;
            i--;
        }
        if(cur == null) return null;
        return cur.val;
    }
    public void set(int i, T val){
        Node<T> cur = this.head.next;
        Node<T> pre = this.head;
        while(i > 0){
            cur = cur.next;
            pre = pre.next;
            i--;
        }
        Node<T> node = new Node<>(val,cur);
        pre.next = node;
    }
    public int size(){
        int cnt = 0;
        Node<T> cur = this.head.next;
        while(cur != null){
            cnt++;
            cur = cur.next;
        }
        return cnt;
    }

    @Override
    public String toString() {
        Node<T> cur = this.head.next;
        String str = "";
        while(cur != null){
            str += cur.toString()+(cur.next!=null?",":"");
            cur = cur.next;
        }
        return str;
    }

    public Node<T> insert(int i, T x){
        if(x == null){
            return null;
        }
        Node<T> pre = this.head;
        for (int j = 0; j < i && pre.next != null; j++) {
            pre = pre.next;
        }
        pre.next = new Node<>(x,pre.next);
        return pre.next;
    }
    public Node<T> insert(T x){
        return insert(Integer.MAX_VALUE, x);
    }
    public static <T> void reserve(SinglyList<T> list){
        Node<T> prev = null;
        Node<T> cur = list.head.next;
        while(cur != null){
            Node<T> curNext = cur.next;
            cur.next = prev;
            prev = cur;
            cur = curNext;
        }
        list.head.next = prev;
    }
    public T remove(T key){
        Node<T> cur = this.head;
        while(cur != null && cur.next != null){
            if(key.equals(cur.next.val)){
                cur.next = cur.next.next;
                return key;
            }
            cur = cur.next;
        }
        return null;
    }

    void removeAllMatched(SinglyList<T> pattern){
        if(pattern.head.next == null) return;
        Node<T> cur = this.head.next;
        Node<T> pre = this.head;
        while(cur != null){
            pre = search(pattern.head.next.val, pre);
            cur = pre.next;
            Node<T> patternCur = pattern.head.next;
            while(cur != null && patternCur != null){
                if(patternCur.val.equals(cur.val)){
                    cur = cur.next;
                    patternCur = patternCur.next;
                }else{
                    break;
                }
            }
            if(patternCur == null){//如果有相同的子串
                pre.next = cur;
            }else if(cur != null){
                cur = cur.next;
            }
        }
    }
    Node<T> search(T val, Node<T> cur){
        Node<T> pre = cur;
        //防止第一个节点和。。 相同
        if(pre == this.head.next && pre.val.equals(val)){
            return this.head;
        }
        //找到和 x 相同节点的前一个节点
        while(pre.next != null && !pre.next.val.equals(val)){
            pre = pre.next;
        }
        return pre;
    }

    public static void main(String[] args) {

        SinglyList<String> singlyList = new SinglyList<>();
        SinglyList<String> pattern = new SinglyList<>();
        for (int i = 1; i < 5; i++) {
            singlyList.insert(""+i);
        }
        for (int i = 1; i < 4; i++) {
            singlyList.insert(""+i);
        }
        for (int i = 0; i < 3; i++) {
            for (int j = 1; j < 5; j++) {
                singlyList.insert(""+j);
            }
        }
        for (int i = 1; i < 4; i++) {
            pattern.insert(i+"");
        }
        System.out.println("初始值: " + singlyList.toString());
        System.out.println("pattern: " + pattern.toString());
        singlyList.removeAllMatched(pattern);
        System.out.println("结果: " + singlyList.toString());
    }
    /*public static void main(String[] args) {
        SinglyList<String> singlyList = new SinglyList<>();
        for (int i = 0; i < 10; i++) {
            singlyList.insert(i+"");
        }
        singlyList.insert("5");
        System.out.println("删除前：" + singlyList.toString());
        singlyList.remove("5");
        System.out.println("删除后：" + singlyList.toString());
        System.out.println("==========");
        System.out.println("逆转前：" + singlyList.toString());
        SinglyList.reserve(singlyList);
        System.out.println("逆转后：" + singlyList.toString());
    }*/
}
